import java.util.*;

class Capitals{
  ArrayList<City> capitals = new ArrayList<City>();

  ArrayList<City> makeCapitals(){
    capitals.add(new City("36105", "Montgomery", "AL", 86.310449, 32.32573));
    capitals.add(new City("85009", "Phoenix", "AZ", 112.128368, 33.456373));
    capitals.add(new City("72201", "Little Rock", "AR", 92.281939, 34.748342));
    capitals.add(new City("95819", "Sacramento", "CA", 121.436634, 38.568293));
    capitals.add(new City("80204", "Denver", "CO", 105.025854, 39.734022));
    capitals.add(new City("06120", "Hartford", "CT", 72.675807, 41.78596));
    capitals.add(new City("19901", "Dover", "DE", 75.535983, 39.156639));
    capitals.add(new City("32304", "Tallahassee", "FL", 84.321132, 30.447752));
    capitals.add(new City("30306", "Atlanta", "GA", 84.351418, 33.786027));
    capitals.add(new City("83705", "Boise", "ID", 116.219104, 43.585077));
    capitals.add(new City("62701", "Springfield", "IL", 89.649531, 39.80004));
    capitals.add(new City("46219", "Indianapolis", "IN", 86.049533, 39.782092));
    capitals.add(new City("50314", "Des Moines", "IA", 93.632993, 41.603003));
    capitals.add(new City("66610", "Topeka", "KS", 95.746061, 38.982213));
    capitals.add(new City("40212", "Frankfort", "KY", 85.804479, 38.265116));
    capitals.add(new City("70815", "Baton Rouge", "LA", 91.059558, 30.455809));
    capitals.add(new City("04330", "Augusta", "ME", 69.766548, 44.323228));
    capitals.add(new City("21403", "Annapolis", "MD", 76.49103, 38.952394));
    capitals.add(new City("02115", "Boston", "MA", 71.092215, 42.342706));
    capitals.add(new City("48823", "Lansing", "MI", 84.476409, 42.738805));
    capitals.add(new City("55103", "Saint Paul", "MN", 93.121594, 44.960798));
    capitals.add(new City("39209", "Jackson", "MS", 90.244626, 32.318422));
    capitals.add(new City("65101", "Jefferson City", "MO", 92.152462, 38.546212));
    capitals.add(new City("59635", "Helena", "MT", 111.905089, 46.597324));
    capitals.add(new City("68503", "Lincoln", "NE", 96.676623, 40.823339));
    capitals.add(new City("89704", "Carson City", "NV", 119.828624, 39.089756));
    capitals.add(new City("03301", "Concord", "NH", 71.527734, 43.218525));
    capitals.add(new City("08618", "Trenton", "NJ", 74.782062, 40.237687));
    capitals.add(new City("87505", "Santa Fe", "NM", 105.981994, 35.619623));
    capitals.add(new City("12207", "Albany", "NY", 73.752327, 42.658133));
    capitals.add(new City("27606", "Raleigh", "NC", 78.711189, 35.764499));
    capitals.add(new City("58501", "Bismarck", "ND", 100.774755, 46.823448));
    capitals.add(new City("43210", "Columbus", "OH", 83.016404, 40.002804));
    capitals.add(new City("73105", "Oklahoma City", "OK", 97.500291, 35.510811));
    capitals.add(new City("97301", "Salem", "OR", 122.979692, 44.926039));
    capitals.add(new City("17101", "Harrisburg", "PA", 76.883079, 40.261767));
    capitals.add(new City("02908", "Providence", "RI", 71.437684, 41.838294));
    capitals.add(new City("29209", "Columbia", "SC", 80.935525, 33.965863));
    capitals.add(new City("57501", "Pierre", "SD", 100.321057, 44.369514));
    capitals.add(new City("37914", "Nashville", "TN", 83.849624, 35.991755));
    capitals.add(new City("78721", "Austin", "TX", 97.686798, 30.272144));
    capitals.add(new City("84103", "Salt Lake City", "UT", 111.874891, 40.777584));
    capitals.add(new City("05602", "Montpelier", "VT", 72.576992, 44.264082));
    capitals.add(new City("23222", "Richmond", "VA", 77.426725, 37.574802));
    capitals.add(new City("98501", "Olympia", "WA", 122.876311, 47.012906));
    capitals.add(new City("25301", "Charleston", "WV", 81.630606, 38.349));
    capitals.add(new City("53714", "Madison", "WI", 89.311758, 43.097735));
    capitals.add(new City("82001", "Cheyenne", "WY", 104.796234, 41.143719));
    return capitals;
  }
  
  
  ArrayList<String> states = new ArrayList<String>();
  
  public ArrayList<String> makeStates(){
    states.add("AL");
    states.add("AZ");
    states.add("AR");
    states.add("CA");
    states.add("CO");
    states.add("CT");
    states.add("DE");
    states.add("FL");
    states.add("GA");
    states.add("ID");
    states.add("IL");
    states.add("IN");
    states.add("KS");
    states.add("KY");
    states.add("LA");
    states.add("ME");
    states.add("MD");
    states.add("MA");
    states.add("MI");
    states.add("MN");
    states.add("MS");
    states.add("MO");
    states.add("MT");
    states.add("NE");
    states.add("NV");
    states.add("NH");
    states.add("NJ");
    states.add("NM");
    states.add("NY");
    states.add("NC");
    states.add("ND");
    states.add("OH");
    states.add("OK");
    states.add("OR");
    states.add("PA");
    states.add("RI");
    states.add("SC");
    states.add("SD");
    states.add("TN");
    states.add("TX");
    states.add("UT");
    states.add("VT");
    states.add("VA");
    states.add("WA");
    states.add("WV");
    states.add("WI");
    states.add("WY");
    return states;
  }
  
  String[][]neighbors = new String[][]{
      {"AL", "MS", "TN", "GA", "FL"},
      {"AZ", "CA", "NV", "UT", "CO", "NM"},
      {"AR", "LA", "TX", "OK", "MO", "TN", "MS"},
      {"CA", "AZ", "NV", "OR"},
      {"CO", "AZ", "UT", "WY", "NE", "KS", "OK", "NM"},
      {"CT", "NY", "MA", "RI"},
      {"DE", "MD", "PA", "NJ"},
      {"FL", "AL", "GA"},
      {"GA", "FL", "AL", "TN", "NC", "SC"},
      {"ID", "NV", "OR", "WA", "MT", "WY", "UT"},
      {"IL", "IN", "KY", "MO", "IA", "WI"},
      {"IN", "MI", "OH", "KY", "IL"},
      {"IA", "IL", "MO", "NE", "SD", "MN", "WI"},
      {"KS", "MO", "OK", "CO", "NE"},
      {"KY", "WV", "VA", "TN", "MO", "IL", "IN", "OH"},
      {"LA", "TX", "OK", "AR", "MS"},
      {"ME", "NH"},
      {"MD", "DE", "PA", "VA"},
      {"MA", "NY", "VT", "NH", "RI", "CT"},
      {"MI", "OH", "IN"},
      {"MN", "WI", "IA", "SD", "ND"},
      {"MS", "AL", "LA", "AR", "TN"},
      {"MO", "IL", "KY", "TN", "AR", "OK", "KS", "NE", "IA"},
      {"MT", "ND", "SD", "WY", "ID"},
      {"NE", "IA", "MO", "KS", "CO", "WY", "SD"},
      {"NV", "CA", "OR", "ID", "UT", "AZ"},
      {"NH", "ME", "MA", "VT"},
      {"NJ", "DE", "PA", "NY"},
      {"NM", "AZ", "UT", "CO", "OK", "TX"},
      {"NY", "VT", "MA", "CT", "NJ", "PA"},
      {"NC", "VA", "TN", "GA", "SC"},
      {"ND", "MN", "SD", "MT"},
      {"OH", "PA", "WV", "KY", "IN", "MI"},
      {"OK", "AR", "TX", "NM", "CO", "KS", "MO"},
      {"OR", "WA", "ID", "NV", "CA"},
      {"PA", "NY", "NJ", "DE", "MD", "VA", "WV", "OH"},
      {"RI", "MA", "CT"},
      {"SC", "NC", "GA"},
      {"SD", "MN", "IA", "NE", "WY", "MT", "ND"},
      {"TN", "NC", "GA", "AL", "MS", "AR", "MO", "KY"},
      {"TX", "NM", "OK", "AR", "LA"},
      {"UT", "CO", "NM", "AZ", "NV", "ID", "WY"},
      {"VT", "NY", "NH", "MA"},
      {"VA", "MD", "PA", "WV", "KY", "TN", "NC"},
      {"WA", "ID", "OR"},
      {"WV", "PA", "VA", "KY", "OH"},
      {"WI", "IL", "IA", "MN"},
      {"WY", "SD", "NE", "CO", "UT", "ID", "MT"}};
  
  public List<List<String>> neighborlist = 
    Arrays.asList(
        Arrays.asList("AL", "MS", "TN", "GA", "FL"),
        Arrays.asList("AZ", "CA", "NV", "UT", "CO", "NM"),
        Arrays.asList("AR", "LA", "TX", "OK", "MO", "TN", "MS"),
        Arrays.asList("CA", "AZ", "NV", "OR"),
        Arrays.asList("CO", "AZ", "UT", "WY", "NE", "KS", "OK", "NM"),
        Arrays.asList("CT", "NY", "MA", "RI"),
        Arrays.asList("DE", "MD", "PA", "NJ"),
        Arrays.asList("FL", "AL", "GA"),
        Arrays.asList("GA", "FL", "AL", "TN", "NC", "SC"),
        Arrays.asList("ID", "NV", "OR", "WA", "MT", "WY", "UT"),
        Arrays.asList("IL", "IN", "KY", "MO", "IA", "WI"),
        Arrays.asList("IN", "MI", "OH", "KY", "IL"),
        Arrays.asList("IA", "IL", "MO", "NE", "SD", "MN", "WI"),
        Arrays.asList("KS", "MO", "OK", "CO", "NE"),
        Arrays.asList("KY", "WV", "VA", "TN", "MO", "IL", "IN", "OH"),
        Arrays.asList("LA", "TX", "OK", "AR", "MS"),
        Arrays.asList("ME", "NH"),
        Arrays.asList("MD", "DE", "PA", "VA"),
        Arrays.asList("MA", "NY", "VT", "NH", "RI", "CT"),
        Arrays.asList("MI", "OH", "IN"),
        Arrays.asList("MN", "WI", "IA", "SD", "ND"),
        Arrays.asList("MS", "AL", "LA", "AR", "TN"),
        Arrays.asList("MO", "IL", "KY", "TN", "AR", "OK", "KS", "NE", "IA"),
        Arrays.asList("MT", "ND", "SD", "WY", "ID"),
        Arrays.asList("NE", "IA", "MO", "KS", "CO", "WY", "SD"),
        Arrays.asList("NV", "CA", "OR", "ID", "UT", "AZ"),
        Arrays.asList("NH", "ME", "MA", "VT"),
        Arrays.asList("NJ", "DE", "PA", "NY"),
        Arrays.asList("NM", "AZ", "UT", "CO", "OK", "TX"),
        Arrays.asList("NY", "VT", "MA", "CT", "NJ", "PA"),
        Arrays.asList("NC", "VA", "TN", "GA", "SC"),
        Arrays.asList("ND", "MN", "SD", "MT"),
        Arrays.asList("OH", "PA", "WV", "KY", "IN", "MI"),
        Arrays.asList("OK", "AR", "TX", "NM", "CO", "KS", "MO"),
        Arrays.asList("OR", "WA", "ID", "NV", "CA"),
        Arrays.asList("PA", "NY", "NJ", "DE", "MD", "VA", "WV", "OH"),
        Arrays.asList("RI", "MA", "CT"),
        Arrays.asList("SC", "NC", "GA"),
        Arrays.asList("SD", "MN", "IA", "NE", "WY", "MT", "ND"),
        Arrays.asList("TN", "NC", "GA", "AL", "MS", "AR", "MO", "KY"),
        Arrays.asList("TX", "NM", "OK", "AR", "LA"),
        Arrays.asList("UT", "CO", "NM", "AZ", "NV", "ID", "WY"),
        Arrays.asList("VT", "NY", "NH", "MA"),
        Arrays.asList("VA", "MD", "PA", "WV", "KY", "TN", "NC"),
        Arrays.asList("WA", "ID", "OR"),
        Arrays.asList("WV", "PA", "VA", "KY", "OH"),
        Arrays.asList("WI", "IL", "IA", "MN"),
        Arrays.asList("WY", "SD", "NE", "CO", "UT", "ID", "MT")); 
}
